/**
 * Created by L.jp
 * Description:
 * User: 86189
 * Date: 2022-06-06
 * Time: 23:02
 */
public class Solution2 {
    public static int change(int amount, int[] coins) {
        //递推表达式
        int[] dp = new int[amount + 1];
//初始化 dp 数组，表示金额为 0 时只有一种情况，也就是什么都不装
        dp[0] = 1;
        for (int i = 0; i < coins.length; i++) {
            for (int j = coins[i]; j <= amount; j++) {
                dp[j] += dp[j - coins[i]];
            }
        }
        return dp[amount];
    }
    
    public static void main (String[] args) {
        int amount=5;
        int[] coins={1, 2, 5};
        System.out.println( change( amount , coins ) );
    }
}
